package com.LeeCode;

/**
 * 统计上升四元组
 */

public class Code2552 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        System.out.println(new Code2552().countQuadruplets(nums));
    }

    public long countQuadruplets(int[] nums) {
        int n = nums.length;
        int[][] great = new int[n][n + 1];
        for (int k = n - 2; k > 0; k--) {
            great[k] = great[k + 1].clone();
            for (int x = 1; x < nums[k + 1]; x++) {
                great[k][x]++;
            }
        }

        long ans = 0;
        for (int j = 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                int x = nums[k];
                if (nums[j] > x) {
                    ans += (long) (x - n + 1 + j + great[j][x]) * great[k][nums[j]];
                }
            }
        }
        return ans;
    }
}
